import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:最小货币数
 * User: wangxin
 * Date: 2025-02-06
 * Time: 21:05
 */
// 第一种方法：动态规划
public class Test {
    public int minMoney (int[] arr, int aim) {
        // write code here
        if(aim < 1){
            return 0;
        }

        int dp[] = new int[aim+1];
        Arrays.fill(dp,aim+1);
        dp[0] = 0;
        for(int i = 1;i < dp.length;i++){
            for(int j = 0;j < arr.length;j++){
                if(arr[j] <= i){
                    dp[i] = Math.min(dp[i],dp[i-arr[j]]+1);
                }
            }
        }
        return dp[aim] > aim?-1:dp[aim];
    }
//===============================================================
    //第二种方法：空间记忆递归
    public int recursion(int[] arr, int aim, int[] dp){
        //组合超过了，返回-1
        if(aim < 0)
            return -1;
        //组合刚好等于需要的零钱
        if(aim == 0)
            return 0;
        //剩余零钱是否已经被运算过了
        if(dp[aim - 1] != 0)
            return dp[aim - 1];
        int Min = Integer.MAX_VALUE;
        //遍历所有面值
        for(int i = 0; i < arr.length; i++){
            //递归运算选择当前的面值
            int res = recursion(arr, aim - arr[i], dp);
            //获取最小值
            if(res >= 0 && res < Min)
                Min = res + 1;
        }
        //更新最小值
        dp[aim - 1] = Min == Integer.MAX_VALUE ? -1 : Min;
        return dp[aim - 1];
    }

    public int minMoney2 (int[] arr, int aim) {
        //小于1的都返回0
        if(aim < 1)
            return 0;
        //dp[i]表示凑齐i元最少需要多少货币数
        int[] dp = new int[aim + 1];
        return recursion(arr, aim, dp);
    }
}
